#-*- coding: utf-8 -*-
"""
Tours de Hanoï - résolution récursive
Par Guillaume HUYSMANS (BA1 info), 2013.

Utilisation : hanoi.py n src dst [/v]
Aucune vérification n'est faite sur n, ça peut durer...
Seules 3 tours sont gérées (limite expliquée dans le code source).
L'option /v permet d'activer les explications (mode verbeux)
"""


def deplacer(n, src, dst, tmp):
	"""
	OPTIMISATION PAS DE MOI :(
	
	Déplace n disques de src vers dst en passant par tmp.
	Ne donne qu'en CSV la liste des mouvements à effectuer.
	Le nombre de mouvements est renvoyé. Ça doit être (2^n)-1.
	
	Cette version utilise un paramètre de moins et fait le minimum,
	elle devrait donc aller (un peu) plus vite que l'autre... De plus, elle ne se 
	plantera pas lorsqu'on lui donnera n=0 : dans ce cas, elle ne fera rien (cas de base !)
	"""
	if n != 0:
		#Étape 1
		ct = deplacer(n-1, src, tmp, dst)
		#Étape 2 directement implémentée ici (pas besoin d'un appel récursif)
		ct += 1 #un seul mouvement (qu'on "fait" tout de suite)
		print '%d;%d' % (src, dst)
		#Étape 3
		ct += deplacer(n-1, tmp, dst, src)
		#Fin
		return ct
	else:
		#bien qu'on ne fasse rien, il faut quand même retourner quelque chose !
		return 0

def deplacer_expl(n, src, dst, tmp, lvl=0):
	"""
	Déplace n disques de src vers dst en passant par tmp.
	Les mouvements sont expliqués dans la console en plus d'être simplement affichés.
	Le nombre de mouvements est renvoyé. Ça doit être (2^n)-1.
	"""
	if n==1:
		#Partie à modifier pour effectuer réellement les mouvements (à l'écran, par exemple).
		#En pratique, on n'a même pas besoin de stocker les positions des disques :
		#tout ce qui est utile tient dans les paramètres !
		print '  '*lvl + "Fait : %d --> %d" % (src, dst)
		return 1
	else:
		print u'  '*lvl + u"But : déplacer %d disques de %d vers %d" % (n, src, dst)
		print u'  '*lvl + u"Étape 1 : %d (n-1) disques vers %d (tmp) en passant par %d (dst)" % (n-1, tmp, dst)
		ct = deplacer_expl(n-1, src, tmp, dst, lvl+1)
		print u'  '*lvl + u"Étape 2 : le dernier disque"
		ct += deplacer_expl(1, src, dst, tmp, lvl+1)
		print u'  '*lvl + u"Étape 3 : %d (n-1) disques de %d (tmp) vers %d (dst) en passant par %d (src)" % (n-1, tmp, dst, src)
		ct += deplacer_expl(n-1, tmp, dst, src, lvl+1)
		return ct

#Suite pas très intéressante, juste une gestion basique de la ligne de commande
#et une astuce pour afficher correctement la doc du module sous Windows.

if __name__ == '__main__':
	import sys
	if len(sys.argv) >= 4:
		#Lecture des paramètres
		n = int(sys.argv[1])
		src = int(sys.argv[2])
		dst = int(sys.argv[3])
		#Gestion des différents cas : rien à faire, hors bornes ou OK
		if src==dst or n==0:
			print u"Rien à faire..."
		elif src<1 or src>3 or dst<1 or dst>3:
			#en fait, la fonction marche très bien pour n'importe quelle valeur,
			#mais ça coincera au niveau de la détermination de la tour temporaire...
			print u"Erreur : seules 3 tours sont gérées..."
		else:
			#TODO y'a plus propre, non ?
			tmp = range(1,4)
			tmp.remove(src)
			tmp.remove(dst)
			tmp = tmp[0]
			#mode verbeux ?
			if (len(sys.argv)==5 and sys.argv[4]=='/v'):
				res = deplacer_expl(n, src, dst, tmp)
			else:
				res = deplacer(n, src, dst, tmp)
			print "\nNombre de mouvements : %d" % res
	else:
		#on affiche la documentation (petite bidouille en ce qui concerne l'encodage)
		print unicode(__doc__, 'utf-8').strip()